//
// Description: 25. K 个一组翻转链表
// Created by Loading on 2021/8/25.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

ListNode *reverseKGroup(ListNode *head, int k) {
    /* 减少头部特判与方便返回翻转结果的头，在 head 前再加一个头结点 */
    auto *hair = new ListNode(0);
    // 本次翻转之前的上一个节点
    auto *pre = hair;

    // 翻转一个长度为 K 的子链表，返回翻转后的头和尾
    auto reverseOneGroup = [k](ListNode *head, ListNode *tail) {
        auto *last = tail->next;
        auto *p = head;
        for (int i = 0; i < k; ++i) {
            auto *temp = p->next;
            p->next = last;
            last = p;
            p = temp;
        }
        return pair<ListNode *, ListNode *>{tail, head};
    };

    while (head) {
        auto *tail = head;
        // 找到一组的 K 个
        for (int i = 0; i < k - 1; ++i) {
            tail = tail->next;
            // 不够 K 个，直接返回
            if (!tail) {
                return hair->next;
            }
        }
        // 本次翻转之后的下一个节点
        auto *next = tail->next;
        /* tie 语法，C++ 17 */
        tie(head, tail) = reverseOneGroup(head, tail);
        // 连接节点
        pre->next = head;
        tail->next = next;
        // 更新 pre
        pre = tail;
        // head 指向下一组的头
        head = next;
    }

    return hair->next;
}

int main() {
    auto *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);
    int k = 2;

    auto res = reverseKGroup(head, k);
    while (res) {
        cout << res->val << " ";
        res = res->next;
    }
    cout << endl;
    return 0;
}